package com.atguigui.leetcode;

/**
 * 775.全局倒置与局部倒置
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/11/16 10:48
 */
public class P775GlobalAndLocalInversions {
    public static void main(String[] args) {
        Solution solution = new P775GlobalAndLocalInversions().new Solution();
        // TO TEST
    }

    class Solution {

        /**
         * 暴力，超出时间限制
         *
         * @param nums
         * @return
         */
        public boolean isIdealPermutation(int[] nums) {
            int n = nums.length, equality = 0;
            for (int i = 0; i < nums.length - 1; i++) {
                //局部倒置
                if (nums[i] > nums[i + 1]) ++equality;
                for (int j = i + 1; j < n; j++) {
                    //全局倒置
                    if (nums[i] > nums[j]) --equality;
                }
            }
            return equality == 0;
        }


        /**
         * 只要是局部倒置的，一定是全局倒置
         *
         * @param nums
         * @return
         */
        public boolean isIdealPermutation1(int[] nums) {
            int n = nums.length;
            for (int i = 0, j = i + 2; i < n - 2; ) {
                //全局倒置不是局部倒置
                //局部倒置：nums[i] > nums[i + 1]
                if (nums[i] > nums[j]) return false;
                ++j;
                if (j == n) {
                    ++i;
                    j = i + 2;
                }
            }
            return true;
        }


        /**
         * @param nums
         * @return
         */
        public boolean isIdealPermutation2(int[] nums) {
            int n = nums.length, max = nums[0];
            for (int i = 2; i < n; i++) {
                //全局倒置不是局部倒置
                if (max > nums[i]) return false;
                max = Math.max(max, nums[i - 1]);
            }
            return true;
        }
    }
}
